package lc20240614;

import java.util.ArrayList;
import java.util.List;

public class NQueen {
    public static void main(String[] args) {
        NQueen nQueen=new NQueen();
        List<List<String>> lists = nQueen.solveNQueens(7);
        System.out.println("lists = " + lists);
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res=new ArrayList<>();
        //初始化一个棋盘
        List<String> chessBoard=new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringBuilder str=new StringBuilder();
            for (int j = 0; j < n; j++) {
                str.append(".");
            }
            chessBoard.add(str.toString());
        }
//        System.out.println(chessBoard);
        backTrack(res,n,0,chessBoard);
        return res;
    }
    private void backTrack(List<List<String>> res,int n,int row,List<String> chessBoard){
        if (row==n){
            List<String> boardCopy = new ArrayList<>();
            for (String s : chessBoard) {
                boardCopy.add(new String(s));
            }
            res.add(boardCopy);

            return;
        }
        for (int i = 0; i < n; i++) {
            //检查当前摆放的位置合法性
            if (isSafe(chessBoard,row,i)){
                chessBoard.set(row,chessBoard.get(row).substring(0,i)+"Q"+chessBoard.get(row).substring(i+1));
                //回溯
                backTrack(res,n,row+1,chessBoard);
                //恢复到原来的状态。
                chessBoard.set(row,chessBoard.get(row).substring(0,i)+"."+chessBoard.get(row).substring(i+1));
            }
        }
    }
    //判断是否合法
    private boolean isSafe(List<String> chessBoard,int row,int col){
        //检查列是否有皇后冲突
        for (int i = 0; i < row; i++) {
            if (chessBoard.get(i).charAt(col)=='Q'){
                return false;
            }
        }
        //检查左上对角线是否有皇后冲突
        for (int i = row-1,j=col-1; i>=0&&j>=0; i--,j--) {
            if (chessBoard.get(i).charAt(j)=='Q'){
                return false;
            }
        }

        //检查右上对角线是否有皇后冲突
        for (int i = row-1,j=col+1; i>=0&&j<chessBoard.size(); i--,j++) {
            if (chessBoard.get(i).charAt(j)=='Q'){
                return false;
            }
        }
        return true;
    }
}
